package LL4;

public class Main {
    //定义双向链表节点
    static class DoubleListNode {
        private int val; //链表的数据域
        private DoubleListNode prev; //链表的前向指针域
        private DoubleListNode next; //链表的后向指针域

        public DoubleListNode(int val) {
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }

    //双向链表
    static class DoubleList {
        private DoubleListNode head; // 头节点
        private DoubleListNode tail; //尾节点

        //添加节点（尾部）
        public void insetAtEnd(int val) {
            DoubleListNode newNode = new DoubleListNode(val);
            //如果链表没有节点，新创建的节点即为链表节点
            if (this.head == null && this.tail == null) {
                this.head = newNode;
                this.tail = newNode;
                return;
            }
            //新节点添加到尾部
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode; //更新链表的尾部节点
        }

        //添加节点（头部）
        public void insetAtStart(int val) {
            DoubleListNode newNode = new DoubleListNode(val);
            //如果链表没有节点，新创建的节点即为链表节点
            if (this.head == null && this.tail == null) {
                this.head = newNode;
                this.tail = newNode;
                return;
            }
            //新节点添加到头部
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode; //更改链表的head节点
        }

        //双向链表遍历（从前往后）
        public void PrintAtStart() {
            DoubleListNode cur = this.head;
            while (cur != null) {
                System.out.print(cur.val + "\t");
                cur = cur.next;
            }
            System.out.println();
        }

        //双向链表遍历（从后往前）
        public void PrintAtEnd() {
            DoubleListNode cur = this.tail;
            //移动指针变量，循环打印节点值
            while (cur != null) {
                System.out.print(cur.val + "\t");
                cur = cur.prev;
            }
            System.out.println();
        }

        //删除节点（每次只删除一个节点）
        public void delete(int val) {
            DoubleListNode cur = this.head;
            while (cur != null) {
                if (cur.val == val) {
                    //删除节点为：头节点
                    if (cur.prev == null) {
                        this.head = cur.next;
                        cur.next = null;
                        this.head.prev = null;
                        return;
                    }
                    //删除节点为：尾节点
                    if (cur.next == null) {
                        this.tail = cur.prev;
                        cur.prev = null;
                        this.tail.next = null;
                        return;
                    }
                    //普通节点删除（删除节点为cur指向的当前节点）
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    return;
                }
                cur = cur.next;
            }
        }

    }

    public static void main(String[] args) {
        DoubleListNode head = new DoubleListNode(1);
        //1. 添加节点
        DoubleListNode newNode1 = new DoubleListNode(2);
        head.next = newNode1; //链表指针衔接:后向
        newNode1.prev = head; //链表指针衔接:前向

        DoubleListNode newNode2 = new DoubleListNode(3);
        head.next.next = newNode2; //链表指针衔接:后向
        newNode2.prev = head.next;  //链表指针衔接:前向

        //2.遍历链表节点
        //2.1 向后遍历
        System.out.println("********************* 向后遍历 ************************");
        System.out.println(head.val);
        System.out.println(head.next.val);
        System.out.println(head.next.next.val);

        //2.2 向前遍历
        System.out.println("********************* 向前遍历 ************************");
        DoubleListNode cur = head.next.next;
        System.out.println(cur.val);
        System.out.println(cur.prev.val);
        System.out.println(cur.prev.prev.val);

        //3. 删除节点（删除值为2的节点）
        head.next = head.next.next;
        head.next.prev = head;

        System.out.println("#################  方法封装  #####################");
        DoubleList root = new DoubleList();
        //4. 添加链表节点（尾部）
        root.insetAtEnd(1);
        root.insetAtEnd(2);
        root.insetAtEnd(3);
        root.insetAtEnd(4);
        root.insetAtEnd(5);

        //5. 添加链表节点（头部）
        root.insetAtStart(10);
        root.insetAtStart(20);
        root.insetAtStart(30);
        root.insetAtStart(40);
        root.insetAtStart(50);

        System.out.println("************************ 打印链表节点的值（从前往后） *******************************");
        //6. 打印链表节点的值（从前往后）
        root.PrintAtStart();

        System.out.println("************************ 打印链表节点的值（从后往前） *******************************");
        //7. 打印链表节点的值（从后往前）
        root.PrintAtEnd();

        //8. 删除链表中的节点
        root.delete(50);
        root.PrintAtStart();

        root.delete(5);
        root.PrintAtStart();

        root.delete(1);
        root.PrintAtStart();

        root.delete(100);
        root.PrintAtStart();

    }
}
